package jm.algorithm.divide;

/**
 * @Description 最大连续子序列
 * @date 2022/5/20 17:13
 */
public class MaxSubarray {

    public static void main(String[] args) {
        int[] nums = {-2, 1};
        System.out.println(maxSubarray3(nums));
    }

    /**
     * 暴力法最大连续子序列
     * @param nums
     * @return
     */
    static int maxSubarray(int[] nums){
        if (nums == null || nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        for (int begin = 0; begin < nums.length; begin++) {
            for (int end = 0; end < nums.length; end++) {
                int sum = 0;
//               拿到 [begin,end] 区间的值
                // 计算子序列的和
                for (int i = begin; i < end; i++) {
                    sum += nums[i];
                }
                // 将大的值给max
                max = Math.max(max,sum);
            }
        }
        return max;
    }

    /**
     * 暴力法最大连续子序列 - 优化
     * @param nums
     * @return
     */
    static int maxSubarray2(int[] nums){
        if (nums == null || nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        for (int begin = 0; begin < nums.length; begin++) {
            int sum = 0;
            // 拿到 [begin,end] 区间的值
            for (int end = begin; end < nums.length; end++) {
                // 重复利用上次计算得到的和与本次的值进行相加。
                sum += nums[end];
                max = Math.max(max,sum);
            }
        }
        return max;
    }

    /**
     * 分治最大连续子序列
     * @param nums
     * @return
     */
    static int maxSubarray3(int[] nums){
        if (nums == null || nums.length == 0) return 0;
        return maxSubarray3(nums, 0, nums.length);
    }

    static int maxSubarray3(int[] nums, int begin, int end){
        // 只有一个元素，不需要分治，即最大和就是第一个元素
        if (end - begin < 2) return nums[begin];

        int mid = (begin + end) >> 1;

        // 左侧子序列最大连续子序列和
        int maxLeft = nums[mid - 1];
        int sumLeft = maxLeft;

        // 计算[begin,mid) 最小序列和
        for (int i = mid - 2; i >= begin; i--) {
            sumLeft += nums[i];
            maxLeft = Math.max(maxLeft,sumLeft);
        }

        // 右侧子序列最大连续子序列和
        int maxRight = nums[mid];
        int sunRight = maxRight;

        // 计算[mid,end) 最小序列和
        for (int i = mid + 1; i < end; i++) {
            sunRight += nums[i];
            maxRight = Math.max(maxRight,sunRight);
        }

        // 获取横跨两部分的最大值
        int max = maxLeft + maxRight;


        return Math.max(max,
                Math.max(
                        maxSubarray3(nums, begin, mid),
                        maxSubarray3(nums, begin, mid)
                )
        );
    }
}
